import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


//园丁题自己想的方法
public class Main {
    public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static String next() throws IOException {
        while(st==null|| !st.hasMoreTokens()){
            st=new StringTokenizer(br.readLine());
        }

        return st.nextToken();
    }

    public static String nextLine() throws IOException{
        return br.readLine();
    }

    public static boolean hasNext() throws IOException {
        return br.ready();
    }

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public static int ret=0;

    public static void main(String[] args) throws IOException {

        int n=nextInt();
        int[] power=new int[n+1];


        for(int i=1;i<=n;i++) power[i]=nextInt();

        Map<Integer, List<Integer>> map=new HashMap<>();

        for(int i=0;i<n-1;i++){
            int a=nextInt();
            int b=nextInt();

            if(b<a){
                int tmp=a;
                a=b;
                b=tmp;
            }


            List<Integer> list = map.getOrDefault(a, new ArrayList<>());
            list.add(b);
            map.put(a,list);
        }

        for(List<Integer> list:map.values()){
            int[] vis=new int[n+1];
            int size= list.size();


            for(int i=0;i<size;i++){
                int index=list.get(i);
                int cur=power[index];
                for(int j=i+1;j<size;j++){
                    int index1=list.get(j);
                    int next=power[index1];
                    long num = (long)cur * next;



                    if(Math.sqrt(num)%1==(double) 0){
                        ret++;
                        break;

                    }
                }

            }



        }



        System.out.println(ret);

    }
}


//deepseek标准解法，很有思维，建议看



 class Main1 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    static List<Integer>[] tree;
    static int[] power;
    static int result = 0;

    public static void main(String[] args) throws IOException {
        int n = nextInt();
        power = new int[n + 1];
        tree = new ArrayList[n + 1];

        for (int i = 1; i <= n; i++) {
            power[i] = nextInt();
            tree[i] = new ArrayList<>();
        }

        // 构建无向树
        for (int i = 1; i < n; i++) {
            int u = nextInt();
            int v = nextInt();
            tree[u].add(v);
            tree[v].add(u);
        }

        boolean[] vis = new boolean[n + 1];
        dfs(1, vis); // 从根节点开始 DFS
        System.out.println(result);
    }

    private static void dfs(int node, boolean[] vis) {
        vis[node] = true;
        List<Integer> children = new ArrayList<>();

        // 收集子节点（未访问的邻居）
        for (int v : tree[node]) {
            if (!vis[v]) {
                children.add(v);
                dfs(v, vis); // 递归处理子节点
            }
        }

        // 只有子节点数 >= 2 时才需要处理
        if (children.size() >= 2) {
            processChildren(children);
        }
    }

    private static void processChildren(List<Integer> children) {
        // 构建冲突图（邻接表）
        Map<Integer, Set<Integer>> conflictGraph = new HashMap<>();
        for (int u : children) {
            conflictGraph.put(u, new HashSet<>());
        }

        for (int i = 0; i < children.size(); i++) {
            int u = children.get(i);
            for (int j = i + 1; j < children.size(); j++) {
                int v = children.get(j);
                long product = (long) power[u] * power[v];
                if (isPerfectSquare(product)) {
                    conflictGraph.get(u).add(v);
                    conflictGraph.get(v).add(u); // 无向图，双向记录
                }
            }
        }

        // 贪心算法：每次选择度数最大的节点加入覆盖集
        Set<Integer> vertexCover = new HashSet<>();
        while (true) {
            int maxDegree = -1;
            int maxNode = -1;

            // 找到当前度数最大的未覆盖节点
            for (int u : conflictGraph.keySet()) {
                int degree = conflictGraph.get(u).size();
                if (!vertexCover.contains(u) && degree > maxDegree) {
                    maxDegree = degree;
                    maxNode = u;
                }
            }

            if (maxDegree <= 0) break; // 无剩余冲突边

            vertexCover.add(maxNode);
            result++; // 修改该节点

            // 移除该节点及其关联的边
            for (int v : conflictGraph.get(maxNode)) {
                conflictGraph.get(v).remove(maxNode);
            }
            conflictGraph.get(maxNode).clear();
        }
    }

    private static boolean isPerfectSquare(long num) {
        long sqrt = (long) Math.sqrt(num);
        return sqrt * sqrt == num;
    }
}


//
//    private static int gcd(int a,int b){
//        while(b!=0){
//            int tmp=b;
//            b=a%b;
//            a=tmp;
//        }
//
//        return a;
//    }
//
//    public static void main(String[] args) throws IOException {
//        long k=nextInt();
//        long t=nextInt();
////        boolean[] is=is(1000001);
//        while(t-->0){
//            int n=nextInt();
//            long num=k;
//            for(int i=0;i<1000001;i++){
//
//                int r=(int)k+i;
//
//
//
//                if(r<1000001&&gcd(r,(int)k+2)==1){
//                    num=r;
//                    break;
//                }
//            }
//
//
//
//            long start=1+k;
//            int count=1;
//
//            while(n>start){
//                start+=num+1;
//                count++;
//            }
//
//            System.out.println(count);
//
//
//
//
//        }
//    }
//
//
//    public static boolean[] is(int n){
//        boolean[] ret=new boolean[n+1];
//        Arrays.fill(ret,true);
//        ret[0]=ret[1]=false;
//
//        for (int i=2;i*i<=n;i++){
//            if(ret[i]){
//                for(int j=i*i;j<=n;j+=i){
//                    ret[j]=false;
//                }
//            }
//
//        }
//
//        return ret;
//    }

//
//    static boolean[][] visRow;
//    static boolean[][] visCol;
//    static int[][] ret=new int[5][5];
//    static int[] up=new int[]{2,2,1,3,3};
//    static int[] down=new int[]{1,4,2,2,3};
//    static int[] left=new int[]{2,2,3,2,1};
//    static int[] right=new int[]{3,3,1,2,4};

//
//    public static void main(String[] args) {
//
//        visCol=new boolean[5][6];
//        visRow=new boolean[5][6];
//
//
//        dfs(0,0);
//
//        for (int i = 0; i < 5; i++) {
//            for (int j = 0; j < 5; j++) {
//                System.out.print(ret[i][j]);
//
//            }
//
//        }
//    }
//
//    private static boolean dfs(int row,int col) {
//
//        if(row>=5){
//            return true;
//        }
//
//        if(col>=5){
//            return dfs(row+1,0);
//
//        }
//
//        for(int i=1;i<=5;i++){
//            if(visRow[row][i]||visCol[col][i]) continue;
//            ret[row][col]=i;
//
//            if(col==4){
//                int max=0;
//                int count=0;
//                for(int j=0;j<5;j++){
//                    if(ret[row][j]>max){
//                        count++;
//                        max=ret[row][j];
//                    }
//                }
//                if(count!=left[row]) continue;
//            }
//
//            if(col==4){
//                int max=0;
//                int count=0;
//                for(int j=4;j>=0;j--){
//                    if(ret[row][j]>max){
//                        count++;
//                        max=ret[row][j];
//                    }
//                }
//                if(count!=right[row]) continue;
//            }
//
//            if(row==4){
//                int max=0;
//                int count=0;
//                for(int j=0;j<5;j++){
//                    if(ret[j][col]>max){
//                        count++;
//                        max=ret[j][col];
//                    }
//                }
//                if(count!=up[col]) continue;
//            }
//
//            if(row==4){
//                int max=0;
//                int count=0;
//                for(int j=4;j>=0;j--){
//                    if(ret[j][col]>max){
//                        count++;
//                        max=ret[j][col];
//                    }
//                }
//                if(count!=down[col]) continue;
//            }
//
//            visCol[col][i]=true;
//            visRow[row][i]=true;
//
//            if(dfs(row,col+1)) return true;
//
//            visCol[col][i]=false;
//            visRow[row][i]=false;
//
//
//        }
//
//        return false;
//
//
//    }


//    public static void main(String[] args) {
//        long ret=34;
//        for(int i=4;i<20240601;i++){
//           ret=ret+(long)i*7-(2*(i-1)+1);
//
//        }
//        System.out.println(ret);
//
//    }

//
//public void solve() {
//    int k = io.nextInt();
//    TreeMap<Integer, Integer> map = new TreeMap<>();
//    map.put(1, 1);
//    int l = k + 2, cnt = 2;
//    while (l <= 1000000) {
//        int r = l + k;
//        while (gcd(l, r) > 1) {
//            r++;
//        }
//        map.put(l, cnt);
//        l = r + 1;
//        cnt++;
//    }
//    int n = io.nextInt();
//    for (int i = 0; i < n; i++) {
//        int x = io.nextInt();
//        int res = map.floorEntry(x).getValue();
//        io.println(res);
//    }
//}
//    static int gcd(int a, int b) {
//        return b == 0 ? a : gcd(b, a % b);
//    }
//}







class T{
    public static void main(String[] args) {
        Set<Integer> set=new HashSet<>();
        set.add(1);
        set.add(12);
        set.add(13);
        set.add(14);
        System.out.println(set);
        set.clear();
        System.out.println(set);

    }
}